//
// Created by Administrator on 2023/10/12.
// 素数, 线性筛法
/*
 * 讲解
 * B站:【线性筛素数】 https://www.bilibili.com/video/BV1BV4y177b3/?share_source=copy_web&vd_source=039990b6433b5af9bd2905234cc47ac6
 * https://zhuanlan.zhihu.com/p/146418699
 * https://blog.csdn.net/GD_ONE/article/details/104660294
 *
 * https://oj.hterobot.com/?#/question/107719?order=ID&offset=0&limit=20&teamid&name=%E7%B4%A0%E6%95%B0&range=public
 * 21个测试用例:
 * 
 * https://www.luogu.com.cn/problem/P3912
 * 10个测试用例:
 * int, long long都一样
*/
// 有点问题 再研究 n太大就崩溃

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
    int n = 100;
    n = 1740948; // out: 130971
    n = 2115790; //out:156902
//    n=91571465;// out: 5302853
//    n = 65090061389;//out: 2728793966
//    cin>>n;
    vector<int> primeNum;
    bool isPrime[n + 1] = {0};
    for (int i = 2; i < 1 + n; ++i)
        isPrime[i] = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (isPrime[i])
            primeNum.push_back(i);
        for (int j = 0; j < primeNum.size() && i * primeNum[j] <= n; ++j)
        {
            isPrime[i * primeNum[j]] = 0;
            // 如果这两个因数不能互质, 说明还有后边还有能互质的组合消掉它, 所以就跳出
            if (i % primeNum[j] == 0)
                break;
        }
    }
//    int count = 0;
//    for (int i; i < n + 1; ++i)
//    {
//        if (isPrime[i])
//            count++;
//    }
//    cout<<count;
    cout << primeNum.size() ;
    return 0;
}
